1. Field of the Invention
The present invention relates to a scalable binary shape encoding/decoding method, and more particularly, to a generalized scan interleaving-based encoding/decoding method using context values of neighboring pixels and an apparatus therefor, and to a linear down/up-sampling apparatus used in the encoding/decoding apparatus.
2. Description of the Related Art
Conventional scan interleaving-based encoding methods using context values of neighboring pixels have a limitation in that only a lower layer which is half the length of, and half the width of a current layer can be used.
To solve the above problem, it is an objective of the present invention to provide a generalized scan interleaving-based encoding/decoding method, which uses context values of neighboring pixels and can use a lower layer which is scaled-down in an arbitrary ratio.
To solve the above problem, it is another objective of the present invention to provide a generalized scan interleaving-based encoding/decoding apparatus, which uses context values of neighboring pixels and can use a lower layer which is scaled-down in an arbitrary ratio.
To solve the above problem, it is still another objective of the present invention to provide a linear down/up-sampling apparatus used in the above encoding/decoding apparatus.
To accomplish the above object of the present invention, there is provided a generalized scan interleaving-based encoding method using context values of neighboring pixels, for encoding pixels which were not sampled during down-sampling, after down-sampling pixels of a current layer in the sampling ratio of m/n in the vertical direction and mxe2x80x2/nxe2x80x2 in the horizontal direction when input shape information are pixels of the current layer, in which m, n and mxe2x80x2, nxe2x80x2 are arbitrary integers (zero is forbidden), and m less than =n and mxe2x80x2 less than =nxe2x80x2, the scan interleaving-based method having the steps of (a) forming a bit stream of a base layer by. encoding, through a predetermined encoding method, the base layer pixels which were down-sampled from the current layer pixels through 2K down-sampling and residual down-sampling in the vertical direction and the horizontal direction, respectively, in which the exponent K satisfies. K=0, 1, 2, . . . ; (b) dividing the current layer pixels into units of a predetermined block; (c) forming bit streams for all blocks of the current layer, by sequentially carrying out forming steps for pixels forming each block of the current layer, the forming steps having the steps of (c1) encoding pixels, which were not sampled when vertical-direction 2L down-sampling was L-times recursively carried out in the step (a), using context values of neighboring pixels, in which L is the largest integer less than or equal to log2(n/m), (c2) encoding pixels, which were not sampled during residual down-sampling in the ratio of [(m2 L)/n] in the vertical direction, using context values of neighboring pixels, (c3) encoding pixels, which were not sampled when horizontal-direction 2K down-sampling was K-times recursively carried out in the step (a), using context values of neighboring pixels, in which K is the largest integer less than or equal to log2(nxe2x80x2/mxe2x80x2), (c4) encoding pixels, which were not sampled during residual down-sampling in the ratio of [(mxe2x80x22K)/nxe2x80x2] in the horizontal direction in the step (a), using context values of neighboring pixels, (c5) forming blocks of encoded bit streams by the block by arraying the bit streams encoded in the steps (c1), (c2), (c3), and (c4) in the order of steps (c4), (c3), (c2) and (c1); and (D) forming scalable bit streams by arraying bit streams of the current layer after the bit streams of the base layer.
Preferably, in the scan interleaving-based encoding method, the vertical-direction 2L down-sampling is for sampling even numbered lines in the lines of pixels; the horizontal-direction 2K down-sampling is for sampling even numbered columns in the columns of pixels; the residual down-sampling in the ratio of [(m2L)/n] in the vertical direction is for sampling m2L lines of n lines of pixels so that lines which are not sampled are allocated evenly and after the lines the sampled lines are located; and the residual down-sampling in the ratio of [(mxe2x80x22K)/nxe2x80x2] in the horizontal direction is for sampling mxe2x80x22K columns of every nxe2x80x2 columns of pixels so that columns which are not sampled are allocated evenly and after the columns the sampled columns are located.
Preferably in the scan interleaving-based encoding method, the vertical-direction 2L down-sampling is for sampling odd numbered lines in the lines of pixels; the horizontal-direction 2K down-sampling is for sampling odd numbered columns in the columns of pixels; the residual down-sampling in the ratio of [(m2L)/n] in the vertical direction is for sampling m2L lines of every n lines of pixels so that lines which are not sampled are allocated evenly and before the lines the sampled lines are located; and, the residual down-sampling in the ratio of [(mxe2x80x22K)/nxe2x80x2] in horizontal direction is to sample mxe2x80x22K columns per nxe2x80x2 columns in the columns of pixels so that columns which are not sampled are allocated evenly and before the columns sampled columns are located.
It is preferred that, before the step (c1), the scan interleaving-based encoding method further has a step of performing binary arithmetic encoding of block encoding types after determining the block encoding types by determining an Exceptional Sample Data Block (ESD-B) in which, in pixel encoding through horizontal-direction scanning for each pixel to be decoded, excluding pixels of the base layer, in pixels forming the blocks, there exist one or more exceptional pixels that is not the same as one of a reference pixel which is located nearest to and above the current pixel to be decoded and a reference pixel which is located nearest to and below the current pixel when the reference pixels are the same, or, in pixel encoding through vertical-direction scanning, there exists one, or more pixels that is not the same as one of a reference pixel which located nearest to and to the left of the current pixel and a reference pixel which is located nearest to and to the right of the current pixel when the reference pixels are the same, or otherwise determining the Transitional Sample Data Block (TSD-B), in which the binary arithmetic encoded block encoding type is located in the front of the bit stream encoded by the block formed in the step (c5).
Preferably in the scan interleaving-based encoding method, the generalized scan interleaving-based encoding using context values of neighboring pixels is for performing arithmetic encoding of all pixels to be decoded in the block using neighboring pixels if the block encoding type is an exceptional block; and if the block encoding type is a transitional block, the generalized scan interleaving-based encoding using context values of neighboring pixels is not encoding Predictive Sample Data (PSD) pixels, each of which, in pixel encoding through horizontal direction generalized scanning for each pixel to be decoded in the block, is the same as both a reference pixel which is located nearest to and above the current pixel to be decoded and a reference pixel which is located nearest to and below the current pixel when the reference pixels are the same, or, each of which, in pixel encoding through vertical direction generalized scanning for each pixel to be decoded in the block, is the same as both a reference pixel which is located nearest to and to the left of the current pixel and a reference pixel which is located nearest to and to the right of the current pixel when the reference pixels are the same, and, for otherwise pixels, that is, TSD pixels, the generalized scan interleaving-based encoding is to perform arithmetic encoding of TSD pixels using neighboring pixels.
Preferably in the generalized scan interleaving-based encoding method, the arithmetic encoding using neighboring pixels is for performing arithmetic encoding of probability values corresponding to context values after obtaining context values by using neighboring pixels which are fully encoded, including, in pixel encoding through vertical-direction generalized scanning, a pixel which is located immediately above and to the left of a current pixel to be encoded, a pixel which is located immediately above of the current pixel, a pixel which is located immediately above and to the right of the current pixel, a pixel which is located immediately to the left of the current pixel, a pixel which is located immediately to the right of the current pixel, a pixel which is located immediately below and to the left of the current pixel, and a pixel which is located immediately to the right below of the current pixel, or, including, in pixel encoding through horizontal direction generalized scanning, a pixel which is located immediately above and to the left of a current pixel to be encoded, a pixel which is located immediately above the current pixel, a pixel which is located immediately above and to the right of the current pixel, a pixel which is located immediately to the left of the current pixel, a pixel which is located immediately below and to the left below of the current pixel, a pixel which is located immediately below the current pixel, and a pixel which is located immediately below and to the right of the current pixel.
Preferably, the generalized scan interleaving encoding method is recursively used in a predetermined method for encoding the base layer pixels in the step (a).
To accomplish the above object of the present invention, there is provided a generalized scan interleaving-based decoding method using context values of neighboring pixels, the generalized scan interleaving-based decoding method using bit streams of a base layer which is obtained by encoding the base layer obtained by down-sampling pixels of the current layer in the sampling ratio of m/n in the vertical direction and mxe2x80x2/nxe2x80x2 in the horizontal direction, and bit streams of the current layer which is obtained by encoding pixels, not sampled during down-sampling, in units of a block, when input shape information are pixels of the current layer, in which m, n, mxe2x80x2, nxe2x80x2 are arbitrary integers (zero is forbidden), and m less than =n, mxe2x80x2 less than =nxe2x80x2, the generalized scan interleaving-based method having the steps of (a) decoding the base layer pixels by a predetermined method which uses the base layer bit streams (b) performing horizontal-direction residual up-sampling, horizontal-direction 2K up-sampling, vertical-direction residual up-sampling, and vertical-direction 2K up-sampling of the base layer pixels in the step (a) in order for the base layer pixels to have the same spatial resolution as the current layer, in which the exponent K satisfies K=0.1, 2, . . . ; (c) dividing the current layer pixels up-sampled in the step (b) into units of a predetermined block; and (d) decoding all blocks of the current layer, by sequentially carrying out decoding steps which include (d1) decoding in units of a block pixels interpolated during horizontal-direction up-sampling in the ratio of [nxe2x80x2/mxe2x80x22K)] by applying generalized scan interleaving-based decoding using context values of neighboring pixels to the current layer bit streams corresponding to the block, in which K is the largest integer less than or equal to log2(nxe2x80x2/mxe2x80x2), (d2) decoding pixels, which were interpolated when horizontal-direction 2K up-sampling was K-times recursively carried out, by K times recursively applying generalized scan interleaving-based decoding using context values of neighboring pixels by the block to the current layer bit streams corresponding to the block, (d3) decoding in units of a block pixels interpolated during vertical-direction residual up-sampling in the ratio of [n/(m2L)] by applying generalized scan interleaving-based decoding using context values of neighboring pixels to the current layer bit streams corresponding to the block, in which L is the largest integer less than or equal to log2(n/m), and (d4) decoding pixels, which were interpolated when vertical-direction 2L up-sampling was L-times recursively carried out, by L times recursively applying generalized scan interleaving-based decoding using context values of neighboring pixels by the block to the current layer bit streams corresponding to the block.
Preferably in the generalized scan interleaving-based decoding method, the vertical-direction residual up-sampling in the ratio of [n/(m2L)] is for interpolating one line for every (m2L)/(nxe2x88x92m2L)th line so that interpolated lines are allocated evenly and located before existing lines; the horizontal-direction residual up-sampling in the ratio of [nxe2x80x2/(mxe2x80x22K)] is for interpolating one column for every (m2K)/(nxe2x88x92m2K)th column so that interpolated columns are allocated evenly and located before existing columns; the vertical-direction 2L up-sampling is for interpolating one line before each line of pixels; and the horizontal-direction 2K up-sampling is for interpolating one column before each column of pixels.
Preferably in the generalized scan interleaving-based decoding method, the vertical-direction residual up-sampling in the ratio of [n/(m2L)] is for interpolating one line for every (m2L)/(nxe2x88x92m2L)th line so that interpolated lines are allocated evenly and located after existing lines; the horizontal-direction residual up-sampling in the ratio of [nxe2x80x2/(mxe2x80x22K)] is for interpolating one column for every (m2K)/(nxe2x88x92m2K)th column so that interpolated columns are allocated evenly and located after existing columns; the vertical-direction 2L up-sampling is for interpolating one line after each line of pixels; and the horizontal-direction 2K up-sampling is for interpolating one column after each column of pixels.
It is preferable that the generalized scan interleaving-based decoding method further has a step for performing binary arithmetic decoding of block encoding types which represent an Exceptional Sample Data Block (ESD-B) in which, in pixel decoding through horizontal-direction generalized scanning for each pixel to be decoded, excluding pixels of the base layer, in pixels forming the block, there exist one or more exceptional pixels that is not the same as one of a reference pixel which is located immediately above the current pixel to be decoded and a reference pixel which is located immediately below the current pixel when the reference pixels are the same, or in pixel decoding through vertical-direction generalized scanning, there exists one or more pixels that is not the same as one of a reference pixel which is located immediately to the left of the current pixel and a reference pixel which is located immediately to the right of the current pixel when the reference pixels are the same, and Transitional Sample Data Block (TSD-B) for otherwise blocks.
Preferably in the generalized scan interleaving-based decoding method, the generalized scan interleaving-based decoding using context values of neighboring pixels is for performing arithmetic decoding of all pixels to be decoded in the block using neighboring pixels if the block encoding type is ESD-B; and if the block encoding type is TSD-B, the generalized scan interleaving-based decoding using context values of neighboring pixels is to restore pixels to be decoded to the same values to reference values for Predictive Sample Data (PSD) pixels, each of which, in pixel decoding through horizontal-direction generalized scanning for each pixel to be decoded in the block, is the same as both a reference pixel which is located immediately above the current pixel to be decoded and a reference pixel which is located immediately below the current pixel when the reference pixels are the same, or, each of which, in pixel decoding through vertical-direction generalized scanning for each pixel to be decoded in the block, is the same as both a reference pixel which is located immediately to the left of the current pixel and a reference pixel which is located immediately to the right of the current pixel when the reference pixels are the same, and, for otherwise pixels, that is, TSD pixels, the generalized scan interleaving-based decoding is to perform arithmetic decoding using neighboring pixels.
Preferably in the generalized scan interleaving-based decoding method, the arithmetic decoding using neighboring pixels is for performing arithmetic decoding by obtaining probability values corresponding to context values after obtaining context values by using neighboring pixels which are fully decoded, including, in pixel decoding through vertical-direction generalized scanning, a pixel which is located immediately above and to the left of a current pixel to be decoded, a pixel which is located immediately above of the current pixel, a pixel which is located immediately above and to the right of the current pixel, a pixel which is located immediately to the left of the current pixel, a pixel which is located immediately to the right of the current pixel, a pixel which is located immediately below and to the left of the current pixel, and a pixel which is located immediately below and to the right of the current pixel, or, including, in pixel decoding through horizontal-direction generalized scanning, a pixel which is located immediately above and to the left of a current pixel to be decoded, a pixel which is located immediately above of the current pixel, a pixel which is located immediately above and to the right above of the current pixel, a pixel which is located immediately to the left of the current pixel, a pixel which is located immediately below and to the left of the current pixel, a pixel which is located immediately below of the current pixel, and a pixel which is located immediately below and to the right below of the current pixel.
Preferably in the generalized scan interleaving-based decoding method, the decoded current layer is used as a base layer in the step (a) and steps (b) through (c) are recursively performed.
To accomplish the above object of the present invention, there is provided a generalized scan interleaving-based encoding apparatus using generalized context values of neighboring pixels, for encoding pixel, which were not sampled during down-sampling for obtaining a base layer, among pixels of blocks which are prepared by dividing a current layer into a plurality of blocks in encoding of a current layer, after down-sampling pixels of the current layer in the sampling ratio of m/n in the vertical direction and mxe2x80x2/nxe2x80x2 in the horizontal direction when input shape information are pixels of the current layer, in which m, n, mxe2x80x2, nxe2x80x2 are arbitrary integers (zero is forbidden), and m less than =n, mxe2x80x2 less than =nxe2x80x2, the generalized scan interleaving-based encoding method having down-sampling means for performing vertical-direction 2K down-sampling, vertical-direction residual down-sampling, horizontal-direction 2K down-sampling and horizontal-direction residual down-sampling of the current layer pixels, in which the exponent K satisfies K=0, 1, 2, . . . ; encoding means for encoding the base layer pixels down-sampled in the down-sampling means; a block-dividing unit for dividing the current layer pixels into units of a predetermined block; vertical-direction 2L encoding means for receiving divided blocks from the block-dividing unit, and performing generalized scan interleaving-based encoding of pixel, which were not sampled when vertical-direction 2L down-sampling processes L-times recursively carried out in the down-sampling means, among received block pixels, using context values of neighboring pixels, in which L is the largest integer less than or equal to log2(n/m); vertical-direction residual encoding means for receiving divided blocks from the block-dividing unit, and performing generalized scan interleaving-based encoding of pixels, which were not sampled during residual down-sampling in the ratio of [(m2L)/n] in the vertical direction in the down-sampling means, among received block pixels, using context values of neighboring pixels; horizontal-direction 2K encoding means for receiving divided blocks from the block-dividing unit, and performing generalized scan interleaving-based encoding of pixel, which were not sampled when horizontal-direction 2K down-sampling is K-times recursively carried out in the down-sampling means among received block pixels, using context values of neighboring pixels, in which K is the largest integer less than or equal to log2(nxe2x80x2/mxe2x80x2); horizontal-direction residual encoding means for receiving divided blocks from the block-dividing unit, and performing generalized scan interleaving-based encoding of pixel, which were not sampled during residual down-sampling in the ratio of [(mxe2x80x22K)/nxe2x80x2] in the horizontal direction in the down-sampling means, among received block pixels, using context values of neighboring pixels; and a multiplexing unit for forming bit streams of the base layer after receiving bit streams from the base layer encoding means; forming bits streams in order of the horizontal-direction residual encoding means, the horizontal-direction 2K encoding means, the vertical-direction residual encoding manes, and the vertical-direction 2L encoding means; forming bit streams of the current layer after receiving unit block bit streams as much as the number of blocks; and connecting the current bit streams to the back of the base layer bit streams and transferring the bit streams.
To accomplish the above object of the present invention, there is provided a generalized scan interleaving-based decoding apparatus using generalized context values of neighboring pixels, for decoding pixel which were not sampled during down-sampling for obtaining a base layer, among pixels of block which are prepared by dividing a current layer into a plurality of blocks in encoding of a current layer, after down-sampling pixels of the current layer in the sampling ratio of m/n in the vertical direction and mxe2x80x2/nxe2x80x2 in the horizontal direction when input shape information are pixels of the current layer, in which m, n, mxe2x80x2, nxe2x80x2 are arbitrary integers (zero is forbidden), and m less than =n, mxe2x80x2 less than =nxe2x80x2, having base layer decoding means for decoding the base layer pixels by using the base layer bit streams; up-sampling means for performing horizontal-direction residual up-sampling, horizontal-direction 2K up-sampling, vertical-direction residual up-sampling, and vertical-direction 2K up-sampling in order to provide base layer pixels with the same spatial resolution as the current layer, in which the exponent K satisfies K=0, 1, 2, . . . ; horizontal-direction residual decoding means for locating values decoded through generalized scan interleaving using the current layer bit streams and context values of neighboring pixels in the place where interpolated pixels are located, when horizontal-direction residual up-sampling of the base layer pixels is carried out in the ratio of [nxe2x80x2/(mxe2x80x22K)], in which K is the largest integer less than or equal to log2(nxe2x80x2/mxe2x80x2); horizontal-direction 2K decoding means for locating values decoded through generalized scan interleaving using the current layer bit steams and context values of neighboring pixels on the place where interpolated pixels are located, when horizontal-direction 2K up-sampling of the base layer pixels which were residual up-sampled in the horizontal direction is carried out K times recursively; vertical-direction residual decoding means for locating values decoded through generalized scan interleaving using the current layer bit streams and context values of neighboring pixels in the place where interpolated pixels are located, when [n/(m2L)] times vertical-direction residual up-sampling of the base layer pixels which were 2K up-sampled in horizontal direction is carried out, in which L is the largest integer less than or equal to log2(n/m); and vertical-direction 2L decoding means for locating values decoded through generalized scan interleaving using the current layer bit streams and context values of neighboring pixels on the place where interpolated pixels are located when vertical-direction 2L up-sampling of the base layer pixels which were residual up-sampled in vertical direction is carried out L times recursively.
To accomplish the above object of the present invention, there is provided a down-sampling apparatus for down-sampling input data in the ratio of m/n, in which m and n are arbitrary integers (zero is forbidden) which satisfy mxe2x89xa6n, the down-sampling apparatus having 2K down-sampling means for sampling one data in every 2K data among input data, in which K is the largest integer less than or equal to log2(n/m); and residual down-sampling means for sampling one data in every {n/(m2K)] data among the data sampled in the 2K down-sampling means.
Preferably in the down-sampling apparatus, the 2K down-sampling means samples one data located in the last of every 2K data; and the residual down-sampling means samples (m2L) data in every n data so that data which were not sampled are allocated evenly and after the data the sampled data are located.
Preferably in the down-sampling apparatus, the 2K down-sampling means samples one data located in the front of every 2K data; and the residual down-sampling means samples (m2L) data in every n data so that data which were not sampled are allocated evenly and before the data the sampled data are located.
To accomplish the above object of the present invention, there is provided an up-sampling apparatus for up-sampling input data in the ratio of n/m, in which m, n are arbitrary integers (zero is forbidden) which satisfy mxe2x89xa6n, having a residual up-sampling unit for interpolating [nxe2x88x92m2K] data in every m2K data among input data, in which K is the largest integer less than or equal to log2(n/m); and a 2K up-sampling unit for interpolating (2Kxe2x88x921) data for each data of the data interpolated in the residual up-sampling unit.
Preferably in the up-sampling apparatus, the residual up-sampling unit interpolates [nxe2x88x92m2K] data for every m2K data so that interpolated data are allocated evenly and each interpolated data has the same value as that of data which is located immediately after the interpolated data; and before each interpolated data the 2K up-sampling unit interpolates (2Kxe2x88x921) data that have the same value as the data.
Preferably in the up-sampling, apparatus, the residual up-sampling unit interpolates [nxe2x88x92m2K] data for every m2K data so that interpolated data are allocated evenly and each interpolated data has the same value as that of data which is located immediately before the interpolated data; and after each interpolated data the 2K up-sampling unit interpolates (2Kxe2x88x921) data that have the same value as the data.